Research in speech and handwriting recognition--the translation of a person's voice or writing into computer readable text has been ongoing since at least the 1960's. The two problems share many common characteristics: processing of a signal with inherent temporal structure, recognition of a well-defined and finite set of symbols (i.e., characters and phonemes), composition of these basic symbols to form words and phrases, and presence of the co-articulation effect. Because of these similarities, techniques developed to solve one problem can often be applied to the other.
In an existing speech recognizer, an unknown waveform is converted by a front-end signal processor into a sequence of acoustic vectors, Y=y.sub.1, y.sub.2, . . . , y.sub.T. Each of these vectors is a compact representation of the short-time speech spectrum covering a uniform period of typically 10 milliseconds. With this input representation, the job of the recognition system is formulated as that of determining the most probable word, or word sequence, W* given the observed vector sequence Y. That is, ##EQU1##
The naive way of finding W* is to enumerate all possible word sequences and compute P(W.vertline.Y) for each of them. This approach is impractical when the number of possible words is large. Instead, potential word sequences are explored in parallel (i.e., in a breadth-first fashion), discarding hypotheses as soon as they become improbable. This search process is referred to in the speech literature as the "beam search". See, for example: R. Haeb-Umbach and H. Ney, "Improvements in time-synchronous beam search for 1000-word continuous speech recognition", IEEE Trans. Speech and Audio Processing, Vol 2, pp 353-356, 1994; or J. J. Odell, V. Valtchev, P. C. Woodland, S. J. Young, "A one pass decoder design for large vocabulary recognition" Proc. Human Language Technology Workshop, Plainsboro, N.J., March, 1994.
To further understand the search process, let D={W.sub.1, W.sub.2, . . . , W.sub.K } be a dictionary consisting of the K words known to the system. Each of these words W.sub.i is represented as a sequence of phone models W.sub.i =C.sub.i.sub..sub.1 C.sub.i.sub..sub.2 . . . C.sub.i.sub..sub.L corresponding to its pronunciation (in handwriting recognition there are character models instead). The dictionary is represented in a tree-based structure: at the start there is a branch to every possible start model C.sub.j.sub..sub.1 ; all first models are then connected to all possible follow models C.sub.j.sub..sub.2 and so on. The tree is extended deep enough until all words in D are represented. Word sequences are represented in a compact way by allowing the tree to be reentrant: it is possible to have a path from the start node to some point in the tree corresponding to an end of word, and continuing at the start of the tree again.
The dictionary tree is used by the search to generate a set of initial hypotheses or theories. At each time step, the observed input y.sub.t is compared against the set of open theories, and a probability of each theory generating the input is multiplied into the theory's ongoing score. At any time, a theory is a product of n probabilities, one for each time step. The theories can be directly compared, and some subset may be selected for further evaluation. Each theory has the possibility of propagating to generate a set of new theories that encode possible completions of the utterance from the current point in time. By carefully controlling the rate of new theory propagation and the destruction of obsolete theories, the exponential growth of the search space can be controlled. In particular, the standard formulation of the search algorithm follows a score-prune-propagate pattern, in which theories are scored, poorly scoring theories are destroyed, and then a subset of the survivors are allowed to propagate.
Probabilities are generated using an HMM representation of each phone model, for example as described in L. R. Bahl, F. Jelinek and R. L. Mercer, "A maximum likelihood approach to continuous speech recognition", IEEE Trans. On Pattern Analysis and Machine Intelligence, pp 179-190, 1983. Phonetic HMMs are finite-state machines with a simple left-right topology, and typically, three emitting states. An HMM changes states once every time unit, and every time that a state, q.sub.j, is entered, an acoustic vector, y.sub.t, is produced as output with probability density b.sub.q.sub..sub.j (y.sub.t). In addition, the transition from state q.sub.i to state q.sub.j is also probabilistic and governed by the discrete probability a.sub.q.sub..sub.i .sub.q.sub..sub.j (see FIG. 1).
FIG. 1 shows a 3 state phoneme model. It is shown connected on the left and right to other models. Associated with each state q.sub.i there is an "emission" probability distribution b.sub.q.sub..sub.j (y.sub.t) and associated with each arc (q.sub.i, q.sub.j) there is a "transition" probability a.sub.q.sub..sub.i .sub.q.sub..sub.j .
The problem of computing P(W.vertline.Y) in (1) is simplified by using Bayes'rule which expresses this probability as ##EQU2##
In Eq. (2), P(W) corresponds to the a priori probability of observing W in the language or application of interest, and thus this probability is determined by a language model. P(Y.vertline.W) represents the probability of observing the vector sequence Y given some specified word sequence W. Alternatively, P(Y.vertline.W) is a measure of similarity between a model for W and the unknown speech Y. A model for W is constructed by concatenating word models which, in turn, are composed of concatenated phonetic HMM models. Note that P(Y) may be neglected (during recognition) since it has no effect on the chosen word sequence.
The required probability P(Y.vertline.W) can be computed by summing over all possible state sequences of length T, Q=q.sub.0. . . q.sub.T, through the states of the given model: ##EQU3##
For computational efficiency, P(Y.vertline.W) is often approximated by finding the sequence of states most likely to have generated the given observations Y, without having to search all possible sequences: ##EQU4##
Efforts to apply this framework to the problem of handwriting recognition have focused on formulating input representation schemes that view the handwriting process as a function of a single independent variable, such as time or one dimensional positioning. In existing handwriting recognition schemes, the pen trajectory {(X(t),Y(t)} is transformed into a continuous-time feature vector sequence F=f.sub.1, f.sub.2, . . . , f.sub.t where each vector f.sub.t encodes local information (e.g., writing direction and curvature) for a data point P(t)=(X(t),Y(t)). Reference can be made, for example to J. Makhoul, T. Starner, R. Schwartz and G. Chou, "On-line cursive handwriting recognition using hidden markov models and statistical grammars", IEEE Conf. on Acoustics, Speech and Signal Processing, Australia, 1994; M. Schenkel, I. Guyon and D. Henderson, "On-line cursive script recognition using time-delay neural networks and hidden markov models", IEEE Conf. on Acoustics, Speech and Signal Processing, Australia, 1994; or S. Manke, M. Finke and A. Waibel, "A fast search technique for large vocabulary on-line handwriting recognition", Fifth International Workshop on Frontiers in Handwriting Recognition (IWFHR5), England, 1996.
With this kind of representation, these systems were able to preserve, with almost no modification, the HMM and tree structured forward search architecture described above. However, many of the more efficient character recognizers in handwriting recognition research do not provide scores which meet the operational requirements of forward search methods--namely, that every character hypothesis be able to be scored at every point in time, and that character scores accumulate monotonically as the search proceeds. If these constraints aren't met, the forward search algorithm can no longer prune theories based on their scores.
Non-cumulative character scores mean that scores can fluctuate dramatically, as the character theory spans an ever-larger region of the ink. At some point, if the theory is correct, it should include exactly the correct amount of ink for the character it proposes, at which point it should score well. Before and after this point, it will either not score at all, or will score (hopefully) poorly. This is illustrated in FIG. 2, which is a sketch showing scores for different "points" or "depths" of ink--i.e. scores for a given character at a given start vector and different end vectors. The sketch of FIG. 2 contrasts with a cumulative score illustrated in FIG. 3, in which a score at a given point (vector) is a multiple or fraction of the score at the preceding point.
It follows from this point that once a theory has been created, there is no choice but to live with it until it expires. Partly this is because it is not known when the theory will span the correct ink and get a good score (as shown in FIG. 2) and partly because if not all of the theories score at a given time, there is no way of comparing theories and discarding those which score poorly. It would seem that being unable to prune low scoring theories would lead to a terrible explosion of the search space, and in fact this can happen if steps are not taken to control the growth of the theory set.
If, once a theory has been created, it has to be maintained until it is certain that the theory can be destroyed, there are two significant conclusions. First, there must be a mechanism to determine when a theory can safely be destroyed because it can no longer score well; second, there must be a conservative process for creating theories and avoiding creating those which are unlikely to score well.